#include <stdio.h>
#include <string.h>
#include <math.h>
#include "stack.h"

//初始化
void Initc(charStack *s)
{
    s->top = -1;
}

//字符栈压栈
int Pushc(charStack *c, char n)
{
    if (c->top < MaxSize)
    {
        c->data[++c->top] = n;
        return 1;
    }
    else
        return 0;
}

//GET栈顶元素
char Gettopc(charStack *c)
{
    return c->data[c->top];
}

//字符栈出栈
char Popc(charStack *c)
{
    return c->data[c->top--];
}

//初始化数据栈
void Initd(dataStack *d)
{
    d->top = -1;
}

//数据栈压栈
int Pushd(dataStack *d, double data)
{
    if (d->top < MaxSize)
    {
        d->data[++d->top] = data;
        return 1;
    }
    else
        return 0;
}

//数据栈出栈
double Popd(dataStack *d)
{
    return d->data[d->top--];
}

int Isop(char n) //当前扫描运算符优先级
{
    switch (n)
    {
    case '(':
        return 6;
    case '+':
    case '-':
        return 2;
    case '*':
    case '/':
    case '%':
        return 4;
    case '$': //开方
    case '^': //平方
    case 's': //sin
    case 'c': //cos
    case 't': //tan
        return 5;
    }
}
int Inop(char n) //栈顶运算符优先级
{
    switch (n)
    {
    case '(':
        return 1;
    case '+':
    case '-':
        return 3;
    case '*':
    case '/':
    case '%':
        return 4;
    case '$': //开方
    case '^': //平方
    case 's':
    case 'c':
    case 't':
        return 5;
    }
}

void Transform(char *s1, char *s2)
{
    int i = 0;
    int j = 0;
    int flag1 = -1; //flag1为0表示上次输出为数字，flag1为1表示上次输出为字符
    int flag2 = -1; //flag2为0表示上次扫描为数字，flag2为1表示上次扫描为运算符，用于区分数字后加空格
    charStack st1;     //暂放运算符
    Initc(&st1);

    while (s1[i] != '\0') //处理负数
    {
        if (s1[0] == '-') //第一位数字为负数时
        {
            j = strlen(s1);
            while (j > 0)
            {
                s1[j + 5] = s1[j];
                j--;
            }
            s1[j++] = '(';
            s1[j++] = '0';
            s1[j++] = '-';
            s1[j++] = '1';
            s1[j++] = ')';
            s1[j] = '*';
        }
        if (s1[i] == '(' && s1[i + 1] == '-') // "(" 之后为负号
        {
            j = strlen(s1);
            while (j > i + 1)
            {
                s1[j + 5] = s1[j];
                j--;
            }
            s1[j++] = '(';
            s1[j++] = '0';
            s1[j++] = '-';
            s1[j++] = '1';
            s1[j++] = ')';
            s1[j] = '*';
            i = i + 5;
        }
        i++;
    }
    i=0;
    j=0;
    while (s1[i] != '\0') //处理正号
    {
        if (s1[0] == '+') //第一位数字为正号时
        {
            j = strlen(s1);
            while (j > 0)
            {
                s1[j + 5] = s1[j];
                j--;
            }
            s1[j++] = '(';
            s1[j++] = '0';
            s1[j++] = '+';
            s1[j++] = '1';
            s1[j++] = ')';
            s1[j] = '*';
        }
        if (s1[i] == '(' && s1[i + 1] == '+') // "(" 之后为+
        {
            j = strlen(s1);
            while (j > i + 1)
            {
                s1[j + 5] = s1[j];
                j--;
            }
            s1[j++] = '(';
            s1[j++] = '0';
            s1[j++] = '+';
            s1[j++] = '1';
            s1[j++] = ')';
            s1[j] = '*';
            i = i + 5;
        }
        i++;
    }

    i = 0;
    j = 0;
    while (s1[i] != '\0')
    {
        if (flag1 == 0 && flag2 == 1) //若上次的输出为数字，上次循环扫描为字符，则表示该数字串结束，则在数字后加空格区分
        {
            s2[j++] = ' ';
            flag1 = 1;
        }
        if (s1[i] >= '0' && s1[i] <= '9' || s1[i] == '.')
        {
            s2[j++] = s1[i];
            flag2 = 0;
            flag1 = 0;
        }
        else if (s1[i] == '+' || s1[i] == '-' || s1[i] == '*' || s1[i] == '/' || s1[i] == '%' || s1[i] == '$' || s1[i] == '^' || s1[i] == 's' || s1[i] == 'c' || s1[i] == 't' || s1[i] == '(')
        {
            flag2 = 1;
            if (st1.top < 0 || Isop(s1[i]) > Inop(Gettopc(&st1))) //当前字符优先级大于栈顶优先级或栈空时当前字符  压入字符栈内
            {
                Pushc(&st1, s1[i]);
            }
            else
            {
                while (st1.top >= 0 && Isop(s1[i]) <= Inop(Gettopc(&st1))) //当前字符小于或者等于栈顶字符时  退栈并输出
                {
                    s2[j++] = Popc(&st1);
                    flag1 = 1;
                }
                if (st1.top < 0 || Isop(s1[i]) > Inop(Gettopc(&st1))) //当前字符优先级大于栈顶优先级或栈空时当前字符  压入字符栈内
                {
                    Pushc(&st1, s1[i]);
                }
            }
        }
        else if (s1[i] == ')')
        {
            flag2 = 1;
            if (Gettopc(&st1) != '(') //若括号仅包含数字则没有输出运算符
            {
                flag1 = 1;
            }
            while (Gettopc(&st1) != '(')
            {
                s2[j++] = Popc(&st1);
            }
            Popc(&st1); //将'('出栈
        }
        i++;
    }
    while (st1.top >= 0) //将栈内剩余的运算符依次退栈输出
    {
        s2[j++] = Popc(&st1);
    }
    s2[j] = '\0';
}

//表达式求值
double Calculate(char *s1)
{
    int i = 0;
    int flag; //char类型转换为double类型的标记
    double data1, data2;
    double sum;
    dataStack dstack;
    Initd(&dstack);
    while (s1[i] != '\0')
    {
        if (s1[i] == '+' || s1[i] == '-' || s1[i] == '*' || s1[i] == '/' || s1[i] == '%') //若为运算符获取栈顶两个元素进行计算
        {
            data1 = Popd(&dstack);
            data2 = Popd(&dstack);
            if (s1[i] == '+')
                Pushd(&dstack, data2 + data1);
            else if (s1[i] == '-')
                Pushd(&dstack, data2 - data1);
            else if (s1[i] == '*')
                Pushd(&dstack, data2 * data1);
            else if (s1[i] == '/')
                Pushd(&dstack, data2 / data1);
            else if (s1[i] == '%')
            {
                int a = data2 / data1;
                Pushd(&dstack, data2 - data1 * a);
            }
        }
        else if (s1[i] == '$' || s1[i] == '^' || s1[i] == 's' || s1[i] == 'c' || s1[i] == 't')
        {
            data1 = Popd(&dstack);
            if (s1[i] == '$')
                Pushd(&dstack, sqrt(data1));
            else if (s1[i] == '^')
                Pushd(&dstack, data1 * data1);
            else if (s1[i] == 's')
                Pushd(&dstack, sin(data1 * PI / 180));
            else if (s1[i] == 'c')
                Pushd(&dstack, cos(data1 * PI / 180));
            else if (s1[i] == 't')
                Pushd(&dstack, tan(data1 * PI / 180));
        }
        else //为数据时转化为double类型压栈
        {
            flag = 0; //初始化为0为整数部分标记，1为小数部分标记
            sum = 0;
            double divider = 1;
            while (s1[i] != '\0' && s1[i] != ' ' && s1[i] != '+' && s1[i] != '-' && s1[i] != '*' && s1[i] != '/' && s1[i] != '%' && s1[i] != '$' && s1[i] != '^' && s1[i] != 's' && s1[i] != 'c' && s1[i] != 't')
            {
                if (s1[i] == '.') //若有小数点，进入小数转化模式
                {
                    flag = 1;
                    i++;
                    continue;
                }
                if (flag == 0)   //计算整数部分
                {
                    sum = sum * 10 + (double)(s1[i] - '0');
                }
                else    //计算小数部分
                {
                    divider = divider * 10;
                    sum = sum + ((double)(s1[i] - '0')) / divider;
                }
                i++;
            }
            if (s1[i] == '+' || s1[i] == '-' || s1[i] == '*' || s1[i] == '/' || s1[i] == '%' || s1[i] == '$' || s1[i] == '^' || s1[i] == 's' || s1[i] == 'c' || s1[i] == 't')
                i--; //转化成功一个数据，若下个字符为运算符，则i--，回到当前运算的数据位置
            Pushd(&dstack, sum);
        }
        i++; //i++准备下一个字符的转换
    }
    return Popd(&dstack);
}
bool judge_infix(char str[])  //判断合法性输入
{
    int temp = 0;
    if (str[0] == '/' || str[0] == '*' || str[0] == '%' || str[0] == '^')
        return false;
    if (str[strlen(str) - 1] < '0' && str[strlen(str) - 1] > '9')
    {
        if (str[strlen(str) - 1] != '^' || str[strlen(str) - 1] != ')')
            return false;
    }

    for (int i = 0; i < strlen(str); i++)
    {
        if (str[i] >= '0' && str[i] <= '9')
        {
            if (str[i + 1] == '$' || str[i + 1] == 's' || str[i + 1] == 'c' || str[i + 1] == 't')
            {
                return false;
            }
        }
        if ((str[i] == 's' || str[i] == 'c' || str[i] == 't' || str[i] == '$'))
        {
            if (str[i + 1] == '\0' || str[i + 1] == 's' || str[i + 1] == 'c' || str[i + 1] == 't' || str[i + 1] == '$' || str[i + 1] == '+' || str[i + 1] == '-' || str[i + 1] == '*' || str[i + 1] == '/' || str[i + 1] == '%')
                return false;
        }

        if ((str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '%'))
        {
            if (str[i + 1] == '\0' || str[i + 1] == '+' || str[i + 1] == '-' || str[i + 1] == '*' || str[i + 1] == '/' || str[i + 1] == '%')
                return false;
        }

        if (str[i] == '^' && str[i + 1] == '^')
        {
            return false;
        }
        if (str[i] == '(')
        {
            if (i == 0 && (str[i + 1] == '*' || str[i + 1] == '/' || str[i + 1] == '%' || str[i + 1] == '^' || str[i + 1] == ')'))
                return false;
            else if (str[i + 1] == '\0' || str[i + 1] == '*' || str[i + 1] == '/' || str[i + 1] == '%' || str[i + 1] == '^')
                return false;
            else if (str[i - 1] >= '0' && str[i - 1] <= '9')
                return false;
            temp++;
        }
        else if (str[i] == ')')
        {
            if (i == 0)
                return false;
            else if (str[i - 1] == '+' || str[i - 1] == '*' || str[i - 1] == '-' || str[i - 1] == '/' || str[i - 1] == '%' || str[i - 1] == 's' || str[i - 1] == 'c' || str[i - 1] == 't' || str[i - 1] == '(')
                return false;
            else if ((str[i + 1] >= '0' && str[i + 1] <= '9'))
                return false;
            temp--;
        }
    }
    if (temp == 0)
        return true;
    return false;
}